import java.util.ArrayList;
import java.util.List;

public class TreeNode {


    private TreeNode leftNode;//左节点
    private TreeNode rightNode;//右节点
    private Integer value;//存放的值

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

//定义构造方法
    public TreeNode(Integer o){
        this(null,null,o);
    }
    public  TreeNode(TreeNode leftNode,TreeNode rightNode,Integer value){
        this.leftNode=leftNode;
        this.rightNode=rightNode;
        this.value=value;
    }

    //开始定义二叉树节点的增查改删

    //定义根节点
    private TreeNode root;
    public  TreeNode getRoot(){
        return root;
    }

    //定义插入方法
    public void insert(Integer value){
        TreeNode newNode=new TreeNode(value);
        if(root==null){
            root=newNode;
            root.setLeftNode(null);
            root.setRightNode(null);
        }else{
            //查找二叉树，判断条件，一个节点的左字数要小于节点，右子树要大于节点
            TreeNode currenNode=root;//定义当前节点，节点从根节点开始匹配
            TreeNode parentNode;//定义一个父节点，等会用来当中间量记录
            while(true){
                if(newNode.getValue()>currenNode.getValue()){//当新增节点的值大于当前值的时候，放入，当前节点的右子树中
                    parentNode=currenNode;
                    currenNode=currenNode.getRightNode();
                    if(currenNode==null){//当当前数的右子树为空的时候，放入当前右子树，右子树存在值的时候，进入下一轮循环
                        parentNode.setRightNode(newNode);
                        return;
                    }
                }else{//当新增节点的值小于当前节点值的时候，放入当前节点的左子树中
                    parentNode=currenNode;
                    currenNode=currenNode.getLeftNode();
                    if(currenNode==null){
                        parentNode.setLeftNode(newNode);
                        return;
                    }
                }
            }


        }
    }

    //定义查找方法
    public TreeNode select(Integer i){
        TreeNode currentNode=root;
        while (currentNode.getValue()!=i){
            if(i>currentNode.getValue()){//当值大于当前节点值的时候，进入当前节点的右节点，否则进入左节点
                currentNode=currentNode.getRightNode();
            }else{
                currentNode=currentNode.getLeftNode();
            }
            if(currentNode==null){//如果节点不存在，说明查找值不存在于二叉树中
                return null;
            }
        }
        return currentNode;
    }


    //三种遍历方式
    //1.先序遍历
    public void preorder(TreeNode treeNode){
        if(treeNode!=null){
            System.out.println(treeNode.getValue());
            preorder(treeNode.getLeftNode());
            preorder(treeNode.getRightNode());
        }
    }

    //2.中序遍历
    public void inorder(TreeNode treeNode){
        if(treeNode != null){
            inorder(treeNode.leftNode);
            System.out.println(treeNode.getValue());
            inorder(treeNode.getRightNode());
        }
    }

    //3.后续遍历
    public void afterorder(TreeNode treeNode){
        if(treeNode!=null){
            afterorder(treeNode.getLeftNode());
            afterorder(treeNode.getRightNode());
            System.out.println(treeNode.getValue());
        }
    }


    //节点的删除
    public  void delete(TreeNode treeNode){
        //获取需要删除节点的父节点
        TreeNode parentNode =selectParent(treeNode.getValue());
        TreeNode childNode;


        if(treeNode.getLeftNode()!=null&&treeNode.getRightNode()!=null){//该子树同时存在左节点和右子节点的情况
            //比较麻烦，需要找到所有节点中，最接近的值，来代替该删除节点，使得堆整个数的影响最低
          ArrayList<TreeNode> treeNodeList=putNode(treeNode);
          int i=0;
          while (true){
              if( treeNodeList.get(i)==treeNode){
                  i=i-1;
                  break;
              }else{
                  i++;
              }
          }
          childNode=treeNodeList.get(i);//得到最近值的节点
            //进行节点的替换
            childNode.setRightNode(treeNode.getRightNode());
            childNode.setLeftNode(treeNode.getLeftNode());
            if(treeNode==parentNode.getLeftNode()){//判断删除节点是父节点的左节点或右节点
                parentNode.setLeftNode(childNode);
            }else{
                parentNode.setRightNode(childNode);
            }

        }else if(treeNode.getRightNode()==null&&treeNode.getLeftNode()==null){//该子树没有左子节点和右子节点的处理
            //该节点没有子节点，只需要解除父节点的关系就可以了
            parentNode.setLeftNode(null);
            parentNode.setRightNode(null);

        }else if(treeNode.leftNode!=null){//该节点只有左子节点的情况
            childNode=treeNode.getLeftNode();
            if(treeNode==parentNode.getLeftNode()){//判断删除节点是父节点的左节点或右节点
                parentNode.setLeftNode(childNode);
            }else{
                parentNode.setRightNode(childNode);
            }

        }else if(treeNode.rightNode!=null){//该节点只有右子节点的情况
            childNode=treeNode.getRightNode();
            if(treeNode==parentNode.getLeftNode()){//判断删除节点是父节点的左节点或右节点
                parentNode.setLeftNode(childNode);
            }else{
                parentNode.setRightNode(childNode);
            }

        }
    }

    public TreeNode selectParent(Integer i){//查找父节点
        TreeNode currentNode=root;
        TreeNode parentNode = currentNode;
        while (currentNode.getValue()!=i){
            parentNode=currentNode;
            if(i>currentNode.getValue()){//当值大于当前节点值的时候，进入当前节点的右节点，否则进入左节点
                currentNode=currentNode.getRightNode();
            }else{
                currentNode=currentNode.getLeftNode();
            }
            if(currentNode==null){//如果节点不存在，说明查找值不存在于二叉树中
                return null;
            }
        }
        return parentNode;
    }

    public ArrayList<TreeNode> putNode(TreeNode treeNode){//将一个二叉树按顺序放入集合中
        ArrayList<TreeNode> arrayList=new ArrayList<>();
        if(treeNode != null){
            inorder(treeNode.leftNode);
            arrayList.add(treeNode);
            inorder(treeNode.getRightNode());
        }
        return arrayList;
    }



}
